/**
 * \file ArbreAVL.h
 * \brief Classe définissant un arbre de tri et/ou recherche
 * \author Abder
 * \version 1.1, mise à jour des commentaires Thierry
 * \date 2013-11-15
 *
 * Définition de la classe Arbre et de ses fonctions
 * membres. Représentation par chaînage. L'arbre est
 *  balancé suite aux insertions et suppressions
 */

#ifndef _BST
#define _BST

#include <stdexcept>
#include <iostream>
#include <vector>
#include <queue>

namespace tp3
{
/** 
 * \class Arbre
 *
 * \brief classe générique représentant un arbre
 *
 *  La classe gére un arbre générique. L'implémentation
 *  se fait par chaînage.
 */
template<typename T, typename V>
class ArbreAVL
{
public:

   ArbreAVL();

   ArbreAVL(const ArbreAVL& source) throw (std::bad_alloc);

   ~ArbreAVL();

   //surcharge d'opérateurs
   const ArbreAVL<T, V>& operator =(const ArbreAVL & a) throw (std::bad_alloc);
   bool operator ==(const ArbreAVL &a);

   //Sélecteurs
   bool estVide() const;
   long taille() const;
   int hauteur() const throw (std::logic_error);
   const T& max() const throw (std::logic_error);
   const T& min() const throw (std::logic_error);
   bool appartient(const T &) const;
   int nbFeuilles() const;
   int compterNbNoeuds() const;
   const T& parent(const T&) const;
   V valeur(const T&)const;
   T cle(const V&) const;
   T successeur(const T&) const throw (std::logic_error);

   void lister(T*, int&) const;
   std::vector<std::pair<T, V > > lister() const throw (std::bad_alloc);

   std::vector<std::pair<T, V > > listerPreOrdre() const;
   std::vector<std::pair<T, V > > listerEnOrdre() const;
   std::vector<std::pair<T, V > > listerPostOrdre() const;

   void parcourirPreOrdre(void (*traitement)(T &iteme)) const;
   void parcourirEnOrdre(void (*traitement)(T &iteme)) const;
   void parcourirPostOrdre(void (*traitement)(T &iteme)) const;
   void parcourirParNiveau(void (*traitement)(T &iteme)) const;

   //modificateurs
   void inserer(const T &data, const V &value) throw (std::bad_alloc);
   void enlever(const T&) throw (std::logic_error);

private:
   /**
    * \class Noeud
    *
    * \brief classe interne représentant un noeud typique de l'arbre
    *
    *  La classe représente un noeud typique
    *  pour implémenter un arbre par chaénage.
    */
   class Noeud
   {
   public:
      T info; /*!< La donnée dans l'arbre*/
      V value;
      Noeud *gauche; /*!< Pointeur vers le fils gauche*/
      Noeud *droite; /*!< Pointeur vers le fils droit*/
      int hauteur; /*!< La hauteur d'un noeud, utile pour le critère de balancement*/
      /**
       * \brief Constructeur de la classe Noeud
       *
       * \post un noeud typique est intialisé
       */
      Noeud(const T&d, const V&v) :
            info(d), value(v), gauche(0), droite(0), hauteur(0)
      {
      }
   };

   // Les membres données
   Noeud * racine;
   long nbNoeudsDansArbre;

   // Les membres fonctions privés

   // Les auxiliaires récursifs
   const T & _max(Noeud*) const throw (std::logic_error);
   const T & _min(Noeud*) const throw (std::logic_error);
   int _hauteur(Noeud *) const;
   int _hauteurParcours(Noeud *) const;
   int _nbFeuilles(Noeud*) const;
   int _nbNoeuds(Noeud*) const;

   Noeud* _auxAppartient(Noeud* arbre, const T &data) const;

   Noeud* _parent(Noeud*, Noeud*) const throw (std::logic_error);
   T _successeur(Noeud*, const T&) const throw (std::logic_error);

   bool _auxArbresEgaux(Noeud *, Noeud *);

   void _auxCopier(Noeud *, Noeud*&) throw (std::bad_alloc);
   void _auxDetruire(Noeud * &t);

   void _auxInserer(Noeud *&, const T &, const V&) throw (std::bad_alloc);
   void _auxEnlever(Noeud* &, const T&);
   void _auxRetireMin(Noeud* &);

   void _auxPreOrdre(Noeud *arbre, void (*traitement)(T&iteme)) const;
   void _auxEnOrdre(Noeud *arbre, void (*traitement)(T& iteme)) const;
   void _auxPostOrdre(Noeud * arbre, void (*traitement)(T& iteme)) const;
   void _auxEnOrdre(Noeud*, T*, int&) const;
   void _auxPreOrdre(Noeud*, std::vector<std::pair<T, V > >&) const;
   void _auxEnOrdre(Noeud*, std::vector<std::pair<T, V > >&) const;
   void _auxPostOrdre(Noeud*, std::vector<std::pair<T, V > >&) const;

   // Les membres privés propres aux arbres AVL
   void _zigZigGauche(Noeud *&);
   void _zigZigDroit(Noeud *&);
   void _zigZagGauche(Noeud *&);
   void _zigZagDroit(Noeud *&);

};
}

#include "ArbreAVL.hpp"

#endif

